namespace DynamicProgramming;

public class LC0118
{
    public IList<IList<int>> Generate(int numRows)
    {
        List<IList<int>> ret = new List<IList<int>>(numRows);

        for (int i = 0; i < numRows; i++)
        {
            ret.Add(new List<int>(i));
            for (int j = 0; j < i + 1; j++) // 每一行的元素数量比行号大1
            {
                ret[i].Add(1);
            }

            for (int j = 1; j < i; j++)
            {
                ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
            }
        }

        return ret;
    }
}